Llumnix: Dynamic Scheduling for Large Language Model Serving
作者信息 Biao Sun, Ziming Huang, Hanyu Zhao, Wencong Xiao, Xinyi Zhang, Yong Li, Wei Lin 杨海龙老师组硕士Biao Sun和刘禹老师组硕士Ziming Huang在阿里云实习中和alibaba PhD Hanyu Zhao的工作
链接：[2406.03243] Llumnix: Dynamic Scheduling for Large Language Model Serving
摘要：
Inference serving for large language models (LLMs) is the key to unleashing their potential in people's daily lives. However, efficient LLM serving remains challenging today because the requests are inherently heterogeneous and unpredictable in terms of resource and latency requirements, as a result of the diverse applications and the dynamic execution nature of LLMs. Existing systems are fundamentally limited in handling these characteristics and cause problems such as severe queuing delays, poor tail latencies, and SLO violations. We introduce Llumnix, an LLM serving system that reacts to such heterogeneous and unpredictable requests by runtime rescheduling across multiple model instances. Similar to context switching across CPU cores in modern operating systems, Llumnix reschedules requests to improve load balancing and isolation, mitigate resource fragmentation, and differentiate request priorities and SLOs. Llumnix implements the rescheduling with an efficient and scalable live migration mechanism for requests and their in-memory states, and exploits it in a dynamic scheduling policy that unifies the multiple rescheduling scenarios elegantly. Our evaluations show that Llumnix improves tail latencies by an order of magnitude, accelerates high-priority requests by up to 1.5x, and delivers up to 36% cost savings while achieving similar tail latencies, compared against state-of-the-art LLM serving systems. Llumnix is publicly available at this https URL.
总结概括
支持多节点调度的LLM服务系统
Motivation
- Req在内存的动态性
服务请求之间存在干扰
内存碎片问题，按照当前最小内存占用分配请求，依然会面临服务的不均衡。
优先级
Rescheduling
之前的工作只是关注在单机的吞吐最大化，请求会在最开始的时候，而忽视了多实例的协同。即使我们服务器有足够的服务能力，某个请求也可能会在一开始就被绑定在某个节点上一直排队。
Design
四种调度理念：
- 图a的负载均衡(load balancing)，根据所用内存，尽量保证各节点的负载是均衡的。但又因为输出长度是不确定的，可能会面临两个问题： higher memory fragmentation and longer queuing delays of long inputs probably.
- 图b的去碎片化(de-fragmentation)，通过去碎片化获得更完整的内存空间，使得新的长请求可以被调度。
- 图c的优先级(prioritization) ，通过调度使得高优先级的请求获得更低的负载和更少的干扰，为高优先级请求保留了更多的资源。
- 图d的自动缩放(auto-scaling)，支持释放某些机器。
然而，跨机器的调度会带来不可接受的延迟，Llumnix针对这个问题提出了不停机的迁移机制。
假如需要开始Migration
- Stage0：（橙色计算块）继续计算，并且同时进行之前计算出来的（绿色内存块）KV Cache迁移。
- Stage1：（蓝色计算块）继续计算，并且同时进行在Stage1时计算出来的（橙色内存块）KV Cache迁移。
- 因为随着传输比计算快，所以随着Stage的进展，需要传输的数据越来越少，传输的时间也越来越短。
- 直到Stage N的时候，只生成了一个iteration的KV Cache，这时候就停止原instance的继续计算，并传输KV Cache到新的instance。就能够在很短的时间内完成了数据迁移。
这里引入了虚拟机实时迁移的概念，但也会带来新的挑战：然而，这种方式又会遇到一种问题，迁移是需要持续较长一段时间的，请求可能在这段时间已经结束了。【异常处理问题】
- 在每一个Stage迁移前，原instance会发送疫情PRE-ALLOC或ABORT请求，前者包含需要的块信息。如果在新的round中，
- 在每一个Stage迁移后，目标instance会发送一个ACK或ABORT请求。
至此，Live Migration已经实现，为了保证LLumnix的持续性调度功能，还需要设计一个可以支持持续跟踪和重新调度的系统。
为了实现跨instance的功能，Llumnix将负载解耦出来提供给Global Scheduler，这是一个仅关注各instance Load的调度器，对内部细节并不关注。Global Scheduler按照Load分发Request以及根据Load启动Migration请求。Llumlet则是各节点的具体调度器，负责实际的调度工作，除此之外还支持汇报Load给Global Scheduler、接收到Migration请求后做实际的Live Migration操作。
那么，实际的调度策略又应该如何实现呢？如何实现一个同时支持负载均衡和负载不均衡（碎片化、优先级、scaling）的系统呢？LLumnix引入了另外一个机制：虚拟内存。
为了去碎片化，Llumnix会把queue排第一位的序列的空间预先分配在虚拟内存中，尽管物理上它还未进入推理。通过这种方法，可以给长队列迁移或预留出足够的空间。同时，采用了一种虚拟内存的启发式方法：逐渐增加其虚拟内存，直到达到真正的内存需求。
为了保证请求的优先级差异，Llumnix通过提供一个Headroom给高优先级请求，这使得高优先级请求有预留的充足空间来进行推理。这个Headroom是节点内所有高优先级请求共享的，通过这种方式可以更方便地拓展于多优先级的情况。
为了实现auto scaling，我们会将某个instance上分配使用无穷大的虚拟内存的假请求。
除此之外，Llumnix还引入了一个Freeness的指标来代表该节点内存消耗的速度。并定期选择Freeness最小和最大的两个节点，触发其Migration机制。假如在某段时间内Freeness超过或者小于某个值，则触发AutoScaling
创新点
- 带有isolation、priority的调度
- 动态迁移实现上下文切换机制